package 中等.队列;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 给定一个整数数组 nums 和一个整数 k ，请返回其中出现
 * 频率前 k 高的元素。可以按 任意顺序 返回答案。
 * 进阶：所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/g5c51o/
 */
public class 出现频率最高的k个数字_offer060 {

    public static void main(String[] args) {

    }

    /**
     * 哈希表统计数字频率+排序
     * 时间复杂度 O(n log(n)) 不满足题目要求
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int[][] freq = new int[map.size()][2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            freq[idx++] = new int[]{entry.getKey(), entry.getValue()};
        }
        Arrays.sort(freq, (a, b) -> b[1] - a[1]);
        int[] topK = new int[k];

        for (int i = 0; i < k && i < freq.length; i++) {
            topK[i] = freq[i][0];
        }
        return topK;
    }

    /**
     * 哈希表统计频率+优先队列
     * 队列中永远只保存 k 个元素，所有每次 add(),remove() 的时间复杂度是 log(k)
     * 总共时间复杂度为 O(n log(k))
     */
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 将频率低的数字放在堆顶，便于取出
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
            } else if (entry.getValue() > priorityQueue.peek()[1]) {
                priorityQueue.poll();
                priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
            }
        }

        int[] topK = new int[k];
        for (int i = 0; i < topK.length; i++) {
            topK[i] = priorityQueue.poll()[0];
        }
        return topK;
    }

}
